
from math import inf

class Solution:
    def maxPathSum(self, root) -> int:

        ans = -inf

        def dfs(node) -> int:
            if not node:
                return 0
            
            l_val = dfs(node.left)
            r_val = dfs(node.right)
            nonlocal ans
            # 因为l_val 和 r_val 都是非负的，很关键
            ans = max(ans, l_val + r_val + node.val)
            # 只需要贡献半侧的最大值和最小值节点
            return max(max(l_val, r_val) + node.val, 0)
        
        dfs(root)

        return ans

